Collective Influence Algorithm to find influencers via optimal percolation in massively large social media

摘要

We elaborate on a linear time implementation of the Collective Influence (CI)algorithm introduced by Morone, Makse, Nature 524, 65 (2015) to find theminimal set of influencers in a network via optimal percolation. We show thatthe computational complexity of CI is O(N log N) when removing nodesone-by-one, with N the number of nodes. This is made possible by using anappropriate data structure to process the CI values, and by the finite radius lof the CI sphere. Furthermore, we introduce a simple extension of CI when l isinfinite, the CI propagation (CI_P) algorithm, that considers the globaloptimization of influence via message passing in the whole network andidentifies a slightly smaller fraction of influencers than CI. Remarkably, CI_Pis able to reproduce the exact analytical optimal percolation thresholdobtained by Bau, Wormald, Random Struct. Alg. 21, 397 (2002) for cubic randomregular graphs, leaving little improvement left for random graphs. We alsointroduce the Collective Immunization Belief Propagation algorithm (CI_BP), abelief-propagation (BP) variant of CI based on optimal immunization, which hasthe same performance as CI_P. However, this small augmented performance of theorder of 1-2 % in the low influencers tail comes at the expense of increasingthe computational complexity from O(N log N) to O(N^2 log N), rendering both,CI_P and CI_BP, prohibitive for finding influencers in modern-day big-data. Thesame nonlinear running time drawback pertains to a recently introducedBP-decimation (BPD) algorithm by Mugisha, Zhou, arXiv:1603.05781. For instance,we show that for big-data social networks of typically 200 million users (eg,active Twitter users sending 500 million tweets per day), CI finds theinfluencers in less than 3 hours running on a single CPU, while the BPalgorithms (CI_P, CI_BP and BDP) would take more than 3,000 years to accomplishthe same task.